Duck's Blog

热爱 Coding 的普通人

Codeforces Round #102 (Div. 2)

发布于 2022-09-20 | 标签: CF | 9分钟 | 1452字数

A

弱智题，暴力枚举即可。

Code

#include <cstdio>

int a[4], row[2], col[2], dia[2], vis[9], flag;

int main() {
    scanf("%d%d%d%d%d%d", &row[0], &row[1], &col[0], &col[1], &dia[0], &dia[1]);
    for (a[0] = 1; a[0] <= 9; a[0]++) {
        for (a[1] = 1; a[1] <= 9; a[1]++) 
            for (a[2] = 1; a[2] <= 9; a[2]++) 
                for (a[3] = 1; a[3] <= 9; a[3]++) 
                    if (a[0] + a[1] == row[0] && a[2] + a[3] == row[1]
                     && a[0] + a[2] == col[0] && a[1] + a[3] == col[1]
                     && a[0] + a[3] == dia[0] && a[1] + a[2] == dia[1]
                     && a[0] != a[1] && a[1] != a[2] && a[2] != a[3]
                     && a[0] != a[3] && a[0] != a[2] && a[1] != a[3]) {
                         printf("%d %d\n%d %d", a[0], a[1], a[2], a[3]);
                         return 0;
                     }
    }
    puts("-1");
    return 0;
}

B

弱智字符串模拟，时间复杂度 O(n)O(n) 。

Code

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;

int main() {
    string s; cin >> s;
    if (s[0] == '-') putchar('(');
    putchar(""); // 不知道为什么美元符号放在这里会渲染失败，注意这里输出美元符号。
    int pos = -1;
    for (int i = 0; i < s.size(); i++) if (s[i] == '.') { pos = i; break; }
    if (pos == -1) {
        for (int i = 0 + (s[0] == '-'); i < s.size(); i++) {
            putchar(s[i]);
            if ((s.size() - i - 1) % 3 == 0 && i != s.size() - 1) putchar(',');
        }
        printf(".00");
    } else {
        for (int i = 0 + (s[0] == '-'); i < pos; i++) {
            putchar(s[i]);
            if ((pos - i - 1) % 3 == 0 && i != pos - 1) putchar(',');
        }
        putchar('.');
        putchar(isdigit(s[pos + 1]) ? s[pos + 1] : '0');
        putchar(isdigit(s[pos + 2]) ? s[pos + 2] : '0');
    }
    if (s[0] == '-') putchar(')');
    return 0;
}

C

考虑枚举 nn 的约数，得到 (a,b,c)(a,b,c) ，更新答案即可。

时间复杂度 O(n)O(\sqrt{n}) 。

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

#define int long long

vector<int> p;

inline void factor(int x) {
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            p.push_back(i);
            if (i * i != x) p.push_back(x / i);
        }
    }
}

int mn = 0x7fffffffffffffff, mx = -0x7fffffffffffffff;

signed main() {
    int n; scanf("%lld", &n);
    factor(n);
    for (int i = 0; i < p.size(); i++) {
        for (int j = 0; j < p.size(); j++) {
            int a = p[i], b = p[j];
            if (n % (a * b)) continue;
            int c = n / a / b;
            mn = min(min(mn, (a + 1) * (b + 2) * (c + 2)), 
                     min((a + 2) * (b + 1) * (c + 2), 
                         (a + 2) * (b + 2) * (c + 1)));
            mx = max(max(mx, (a + 1) * (b + 2) * (c + 2)), 
                     max((a + 2) * (b + 1) * (c + 2), 
                         (a + 2) * (b + 2) * (c + 1)));
        }
    }
    printf("%lld %lld\n", mn - n, mx - n);
    return 0;
}

D

计数题，但是需要考虑一些细节。

当 n=1n=1 或 m=1m=1 时，全都填上就可以。

当 min⁡{n,m}=2\min\{n,m\}=2 时，我们把棋盘划分成若干个田字格，每两个田字格中一个放满一个放空，最后不足一个田字格的全部填满。容易证明这是最多的方案。

其余情况直接黑白染色即可，易知最多能放 ⌈n×m2⌉\lceil\dfrac{n\times m}{2}\rceil 。

Code

#include <cstdio>
#include <cstdlib>

int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }

int main() {
    int n, m; scanf("%d%d", &n, &m);
    if (min(n, m) == 1) printf("%d\n", max(n, m));
    else if (min(n, m) == 2) {
        if (max(n, m) % 4 <= 2) printf("%d\n", max(n, m) / 4 * 4 + max(n, m) % 4 * 2);
        else printf("%d\n", (max(n, m) / 4 + 1) * 4);
    }
    else printf("%d\n", (n * m + 1) / 2);
    return 0;
}

E

典中典T形骨牌覆盖问题，记忆化爆搜即可。

时间复杂度不会算。

Code

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

int n, m, ans, d[15][15];
char a[15][15], b[15][15];

void dfs(int x, int y, int s) {
    if (x == n) {
        if (s >= ans) {
            ans = s;
            memcpy(b, a, sizeof(b));
        }
        return;
    }
    if (a[x - 1][y - 1] == '.' &&
        a[x - 1][y]     == '.' &&
        a[x - 1][y + 1] == '.' &&
        a[x + 1][y]     == '.' &&
        a[x][y]         == '.') {
        a[x - 1][y - 1] = a[x - 1][y] = a[x - 1][y + 1] = a[x + 1][y] = a[x][y] = 'A' + s;
        if (s + 1 >= d[x][y]) {
            d[x][y] = max(d[x][y], s);
            if (y == m - 1) dfs(x + 1, 2, s + 1);
            else dfs(x, y + 1, s + 1);
        }
        a[x - 1][y - 1] = a[x - 1][y] = a[x - 1][y + 1] = a[x + 1][y] = a[x][y] = '.';
    }
    if (a[x + 1][y - 1] == '.' &&
        a[x + 1][y]     == '.' &&
        a[x + 1][y + 1] == '.' &&
        a[x - 1][y]     == '.' &&
        a[x][y]         == '.') {
        a[x + 1][y - 1] = a[x + 1][y] = a[x + 1][y + 1] = a[x - 1][y] = a[x][y] = 'A' + s;
        if (s + 1 >= d[x][y]) {
            d[x][y] = max(d[x][y], s);
            if (y == m - 1) dfs(x + 1, 2, s + 1);
            else dfs(x, y + 1, s + 1);
        }
        a[x + 1][y - 1] = a[x + 1][y] = a[x + 1][y + 1] = a[x - 1][y] = a[x][y] = '.';
    }
    if (a[x - 1][y - 1] == '.' &&
        a[x][y - 1]     == '.' &&
        a[x][y + 1]     == '.' &&
        a[x + 1][y - 1] == '.' &&
        a[x][y]         == '.') {
        a[x - 1][y - 1] = a[x][y - 1] = a[x][y + 1] = a[x + 1][y - 1] = a[x][y] = 'A' + s;
        if (s + 1 >= d[x][y]) {
            d[x][y] = max(d[x][y], s);
            if (y == m - 1) dfs(x + 1, 2, s + 1);
            else dfs(x, y + 1, s + 1);
        }
        a[x - 1][y - 1] = a[x][y - 1] = a[x][y + 1] = a[x + 1][y - 1] = a[x][y] = '.';
    }
    if (a[x - 1][y + 1] == '.' &&
        a[x][y - 1]     == '.' &&
        a[x][y + 1]     == '.' &&
        a[x + 1][y + 1] == '.' &&
        a[x][y]         == '.') {
        a[x - 1][y + 1] = a[x][y - 1] = a[x][y + 1] = a[x + 1][y + 1] = a[x][y] = 'A' + s;
        if (s + 1 >= d[x][y]) {
            if (y == m - 1) dfs(x + 1, 2, s + 1);
            else dfs(x, y + 1, s + 1);
            d[x][y] = max(d[x][y], s);
        }
        a[x - 1][y + 1] = a[x][y - 1] = a[x][y + 1] = a[x + 1][y + 1] = a[x][y] = '.';
    }
    if (y == m - 1) dfs(x + 1, 2, s);
    else dfs(x, y + 1, s);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            a[i][j] = '.';
    }
    if (n < 3 || m < 3) {
        puts("0");
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++)
                putchar(a[i][j]);
            puts("");
        }
        return 0;
    }
    dfs(2, 2, 0);
    printf("%d\n", ans);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            putchar(b[i][j]);
        puts("");
    }
    return 0;
}
赞赏
# CF
Codeforces Round #104 (Div. 1 & Div. 2) 上一篇
Educational Codeforces Round #135 下一篇
已运行:
浏览数: 次 | 访客数: 人
Powered by Gridea
0%
召唤看板娘